Pollaczek–Khinchine formula

In queueing theory, a discipline within the mathematical theory of probability, the Pollaczek–Khinchine formula is a formula for the mean queue length in a model where jobs arrive according to a Poisson process and service times have a general distribution (an M/G/1 queue). It can also be used to calculate the mean waiting time in such a model.

The formula was first published by Felix Pollaczek^[1] and recast in probabilistic terms by Aleksandr Khinchin^[2] two years later.^[3]^[4]

Mean queue length

The formula states that the mean queue length L is given by^[5]

$L = \rho %2B \frac{\rho^2 %2B \lambda^2 \operatorname{Var}(S)}{2(1-\rho)}$

where

$\lambda$ is the arrival rate of the Poisson process
$1/\mu$ is the mean of the service time distribution S
$\rho=\lambda/\mu$ is the utilization
Var(S) is the variance of the service time distribution S.

For the mean queue length to be finite it is necessary that $\rho < 1$ as otherwise jobs arrive faster than they leave the queue. "Traffic intensity," ranges between 0 and 1, and is the mean fraction of time that the server is busy. If the arrival rate $\lambda_a$ is greater than or equal to the service rate $\lambda_s$ , the queuing delay becomes infinite. The variance term enters the expression due to Feller's paradox.^[6]

Mean waiting time

If we write W for the mean time a customer spends in the queue, then $W=W'%2B\mu^{-1}$ where $W'$ is the mean waiting time (time spent in the queue waiting for service) and $\mu$ is the service rate. Using Little's law, which states that

$L=\lambda W$

where

L is the mean queue length
$\lambda$ is the arrival rate of the Poisson process
W is the mean time spent at the queue both waiting and being serviced,

$W = \frac{\rho %2B \lambda \mu \text{Var}(S)}{2(\mu-\lambda)}.$

We can write an expression for the mean waiting time as^[7]

$W' = \frac{W}{\lambda} - \mu^{-1} = \frac{\rho %2B \lambda \mu \text{Var}(S)}{2(\mu-\lambda)}.$

References

^ Pollaczek, F. (1930). "Über eine Aufgabe der Wahrscheinlichkeitstheorie". Mathematische Zeitschrift 32: 64–100. doi:10.1007/BF01194620.
^ Khintchine, A. Y (1932). "Mathematical theory of a stationary queue". Matematicheskii Sbornik 39 (4): 73–84. http://mi.mathnet.ru/rus/msb/v39/i4/p73. Retrieved 2011-07-14.
^ Takács, Lajos (1971). "Review: J. W. Cohen, The Single Server Queue". Annals of Mathematical Statistics 42 (6): 2162–2164. doi:10.1214/aoms/1177693087.
^ Kingman, J. F. C. (2009). "The first Erlang century—and the next". Queueing Systems 63: 3–4. doi:10.1007/s11134-009-9147-4. edit
^ Haigh, John (2002). Probability Models. Springer. p. 192. ISBN 1852334312.
^ Cooper, Robert B.; Niu, Shun-Chen; Srinivasan, Mandyam M. (1998). "Some Reflections on the Renewal-Theory Paradox in Queueing Theory". Journal of Applied Mathematics and Stochastic Analysis 11 (3): 355–368. http://www.cse.fau.edu/~bob/publications/CNS.4h.pdf. Retrieved 2011-07-14.
^ Harrison, Peter G.; Patel, Naresh M. (1992). Performance Modelling of Communication Networks and Computer Architectures. Addison-Wesley. p. 228. ISBN 0201544199.